1. Field of the Invention
This invention relates to the field of error correction, and more particularly relates to a method and system for a multi-channel add-compare-select unit.
2. Description of the Related Art
The “Add-Compare-Select” (ACS) circuit is a well-known building block for a variety of circuits, including circuits such as the Forward Error Correction (FEC) circuit. The ACS circuit (ACS unit) forms the basis of most convolutional/trellis decoders, as well as comparable circuits. The basic function of an ACS unit is to add its inputs together in some combination, compare the results of those additions, and in doing so, select one of those results as the ACS unit's output.
The function of an ACS unit in a trellis decoder can be used as an example. In the simplest terms, an ACS unit implemented in a trellis decoder takes the cost of each branch into a state within the trellis, and adds the total cost of the source state for that branch. This results in two new state costs (e.g., A and B). These two new state costs are then compared to one another, and the smaller cost of the two is selected (e.g., B<A?). This selected cost is output as the new cost for the current state under consideration. An FEC design may contain hundreds of such ACS units. The output of each of these ACS units feeds back into itself, or to the inputs of another of the ACS units. The ACS units' operation needs to execute in a single symbol period in order to successfully process the incoming data stream. Thus, the ACS unit typically forms the critical timing path within a design employing such circuits (e.g., an FEC design).
FIG. 1 is an example of such an “add-compare-select”(ACS) unit 100 of the prior art. ACS unit 100 includes two adder units (depicted in FIG. 1 as an adder unit 110 and an adder unit 120). Adder unit 110 takes as its input a previous state A cost signal 112 and a branch cost A signal 114. Similarly, adder unit 120 takes as its inputs a previous state B cost signal 122 and a branch cost B signal 124. The outputs of adder units 110 and 120 are fed into a selection circuit 130 and a compare unit 140. The output of selection circuit 130 is stored in a register 150, and upon such storage, appears at an output of register 150 as a new cost signal 155.
As noted, the output of adder units 110 and 120 are also provided to compare unit 140. The output of adder unit 110 is received by compare unit 140 at an input A. Similarly, the output of adder unit 120 is received by compare unit 140 at an input B. Compare unit 140 uses this information to make a determination as to whether the output of adder unit 110 is less than the output of adder unit 120 (depicted in FIG. 1 as an output B<A), and in so doing, for example, determines the smaller of the two new state costs output by adder units 110 and 120.
The output of compare unit 140 is provided to selection unit 130 as a select signal 145. Select signal 145 causes selection unit 130 to select either the output of adder unit 110 or the output of adder unit 120, depending on the outcome of the determination just described. Select signal 145 is also provided to a register 160, which stores select signal 145. Upon storage, this information appears at the output of register 160 as a path selection signal 165.
Similar to the standard ACS unit, the “Add-Compare-Select-Offset” (ACSO) unit operates in a similar manner, with the exception that in an ACSO unit, the larger sum generated is chosen, and a small offset added to that result. Such an architecture is used, for example, in the design of turbo-convolutional decoders, which are an implementation of an advanced Forward Error Correction (FEC) algorithm commonly used in wireless data communications.
FIG. 2 is a block diagram illustrating an architecture of an ACSO unit 200 according to the prior art. As will be appreciated, the architecture of ACSO unit 200 is similar in many respects to that of ACS unit 100 of FIG. 1. In this case, an adder unit 210 takes as its input a previous state A likelihood (PSAL) signal 212 and a branch likelihood A (BLA) signal 214, producing a sum of these two signals. Similarly, an adder unit 220 generates the sum of a previous state B likelihood (PSBL) signal 222 and a branch likelihood B (BLB) signal 224.
Also as before, a selection unit 230 receives these sums (i.e., the outputs of adder units 210 and 220), and selects one of these sums under the control of a compare unit 240. Compare unit 240 receives the sum generated by adder unit 210 at an input A, and receives the sum generated by adder unit 220 at an input B. Compare unit 240 controls the selection made by selection unit 230 based on a comparison of the inputs A and B. Thus, the select signal generated by compare unit 240 is based on a determination as to whether the input B is less than the input A (depicted in FIG. 2 as an output B<A).
However, in ACSO unit 200, compare unit 240 is also configured to generate the difference between input A and input B (depicted in FIG. 2 as an output A-B). This difference is provided as an address to a read-only memory (ROM) 250, or other such storage device. ROM 250 stores offsets that provide the offsets necessary to compute the new likelihood ratio. The outputs of selection unit 230 and ROM 250 are summed by an adder unit 260 to generate a new likelihood value. This new likelihood value is clocked into a register 270, and appears at an output of register 270 as a new likelihood signal 280.
As will be appreciated, it is not uncommon in today's communication systems to have multiple incoming channels. In such a situation, each of these channels needs to be decoded. This has historically been addressed by replicating the decoder circuit once for each additional channel. As will be appreciated, this replication increases the cost of such circuitry, as well as the area consumed. An example of such an architecture is now given.
FIG. 3 is a block diagram depicting a multiple channel architecture 300 of the prior art. Multiple channel architecture 300 includes a number of ACS units (depicted in FIG. 3 as ACS units 310(1)-(N), where N is an integer). Each of ACS units 310(1)-(N) receives an input signal (depicted in FIG. 3 as input signals 320(1)-(N)), representing one of a number of channels of cost data (shown in FIG. 3 as channels 1-N cost data). Correspondingly, each of ACS units 310(1)-(N) generates an output signal (depicted in FIG. 3 as output signals 330(1)-(N)), representing one of a number of channels' new cost data and path selections (shown in FIG. 3 as channels 1-N new cost data and path selections). As will be appreciated, each channel is presented to one of ACS units 310(1)-(N), which performs the requisite decoding, according to the coding/decoding (codec) scheme employed. As will also be appreciated, a multi-channel turbo-convolutional scheme can be implemented by replacing each of ACS units 310(1)-(N) with an ACSO unit.
Such an architecture is not without its limitations, however. While providing for the processing of multiple channels, the usefulness of such an approach is limited by the resources consumed thereby. This is particularly true of the integrated circuit area required by such an architecture. Moreover, while throughput is much improved over a single channel implementation as a result of multiple channels being processed, each ACS unit is still limited to processing a single symbol per symbol time, limiting the architecture's overall throughput. On a per-channel basis, the architecture's throughput is thus no different than that of the single channel implementation. Frequency of operation is similarly restricted, which may result in a substantial portion of a hardware implementation's bandwidth going unused.
What is therefore desired is an ACS/ACSO circuit that is capable of processing multiple data channels. Preferably, such an ACS/ACSO circuit should provide such capabilities with a minimal increase in circuit size as compared to a standard ACS/ACSO circuit. It is also preferable that such a circuit be capable of operating at clock speeds significantly higher than a standard ACS/ACSO circuit.